import numpy as np

n = 3 #选择3:八数码是4：十五数码
class P:
    def __init__(self,matrix,g):
        self.matrix=matrix
        self.father=None
        self.g=g
    def setg(self,g):
            self.g=g
    def setfather(self,B):
        self.father=B
CPLIST=[]#用于未被拓展的储存矩阵
OPLIST=[]#用于已被拓展的储存矩阵
Cvalue=[]#储存未被拓展的矩阵估价函数值
if (n==3):
    L1 = np.mat(np.array([2,8,3,1,0,5,4,7,6]).reshape(3, 3))
    # L1=np.mat(np.array([4,1,3,2,0,5,7,8,6]).reshape(3,3))
elif(n==4):
    L1=np.mat(np.array([1,2,0,5,12,14,4,6,11,13,3,7,10,9,15,8]).reshape(4,4))
P1=P(L1,0)
print("初始矩阵为：\n",P1.matrix)
if (n==3):
    L = np.mat(np.array([1,2,3,4,5,6,7,8,0]).reshape(3, 3))#12
elif(n==4):
    L = np.mat(np.array([1,2,3,4,12,13,14,5,11,0,15,6,10,9,8,7]).reshape(4, 4))#18
Pn=P(L,0)
print("目标矩阵为：\n",Pn.matrix)
CPLIST.append(P1)
def geth(Pa,Pb):#获取两个矩阵每一数码与目标数码之间的距离总和
 num=0
 for x in range(n):
   for y in range(n):
     for i in range(n):
        for j in range(n):
           if (Pa[i,j] == Pb[x,y] & Pb[x,y] != 0):
             num=num+abs(x-i)+abs(y-j)
             break
             break
 return num
def getp(Pa,Pb):#获取两个矩阵每一数码与目标矩阵位置错位的数目
 num=0
 for x in range(n):
   for y in range(n):
     if(Pb[x,y]!=Pa[x,y]):
         if(Pb[x,y]!=0):
           num=num+1
 return num
def switchx(i,P2,x,y):
    P2[x, y], P2[x + i, y] = P2[x + i, y], P2[x, y]
    return getp(Pn.matrix,P2)
def switchy(i,P2,x,y):
    P2[x, y], P2[x, y+i] = P2[x, y+i], P2[x, y]
    return getp(Pn.matrix,P2)
def printf(P0):
    print("倒退路径得：\n")
    while P0.father!=None:
        print(P0.matrix)
        P0=P0.father
    print(P1.matrix)
#移动矩阵（顺序为上下左右）
def move(P0):
 global n
 if (getp(Pn.matrix, P0.matrix)==0):
     print("搜索成功！结束！")
     printf(P0)
     #print("创造节点个数：",len(OPLIST)+len(CPLIST))
     exit()
 for x in range(n):
    for y in range(n):
      if(P0.matrix[x,y]==0):
        P2LIST=[]#储存暂时当前一层矩阵
        if(0 < x & x < n-1):
            if(0 < y & y < n-1):
                #m=4
                for i in (-1,1):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(switchx(i,P2,x,y)+P0.g+1)
                    P2LIST.append(P2)
                for i in (-1,1):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(switchy(i, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
            else:
                #m=3
                for i in (-1, 1):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(switchx(i, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
                if (y==n-1):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(switchy(-1, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
                elif (y==0):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(switchy(1, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
        else:
            if (0 < y & y < n-1):
                #m=3
                if (x == n-1):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(switchx(-1, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
                elif (x == 0):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(switchx(1, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
                for i in (-1, 1):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(switchy(i, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
            else:
                #m=2
                if (x == n-1):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(switchx(-1, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
                elif (x == 0):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(switchx(1, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
                if (y==n-1):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(switchy(-1, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
                elif (y==0):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(switchy(1, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
        f=0
        for PX in CPLIST:
            if (getp(PX.matrix,P0.matrix)==0):
                del CPLIST[f]  #CPLIST删除P0
            f=f+1
        OPLIST.append(P0)      #OPLIST加入P0
        f = 0
        for PX in P2LIST:
            flag = 0
            ZPLIST=CPLIST+OPLIST
            for PY in ZPLIST:  # 防止出现重复的情况
                if (getp(PX, PY.matrix) == 0):
                    flag = 1
            if (flag == 1):
                del P2LIST[f]
            f = f + 1
        for PX in P2LIST:
            PN=P(PX,P0.g+1)#创建节点
            PN.setfather(P0)#构建关系
            #print(PN.g,"深度转换矩阵：\n",PN.matrix)
            #print("估价函数为：",getp(PN.matrix,Pn.matrix)+PN.g)
            CPLIST.append(PN)
        #选择最小值拓展
        #("________\n")
        #print(Cvalue)
        m = min(Cvalue)
        for PX in CPLIST:
            if getp(PX.matrix,Pn.matrix)+PX.g==m:
                #print(PX.g,"拓展矩阵为：\n",PX.matrix)
                Cvalue.remove(m)
                move(PX)

if __name__ == '__main__':
       move(P1)

#0.0.090504,0.090118,0.092403,0.082812 16
#0.048863,0.042844,0.045538,0.040413,0.044170 h 18
#0.009024,0.010930,0.009016,0.008026,0.007978   16
#0.005949,0.024932,0.004987,0.005984,0.006976 p 20